import copy
import time

# question1
N = 6
# 原表
sudoku_map = [[0, 3, 1, 6, 5, 0],
              [6, 0, 0, 0, 0, 4],
              [1, 0, 6, 2, 0, 5],
              [2, 0, 3, 4, 0, 1],
              [5, 0, 0, 0, 0, 3],
              [0, 1, 4, 5, 2, 0]]
# 各块中元素的下标
sudoku_block = []
# 各元素所在块
sudoku_in_block = [[0, 0, 0, 1, 1, 1],
                   [0, 0, 0, 1, 1, 1],
                   [2, 2, 2, 3, 3, 3],
                   [2, 2, 2, 3, 3, 3],
                   [4, 4, 4, 5, 5, 5],
                   [4, 4, 4, 5, 5, 5]]

# question2
# N = 9
# # 原表
# sudoku_map = [[0, 0, 1, 0, 5, 0, 9, 0, 0],
#               [0, 5, 0, 0, 0, 0, 0, 0, 2],
#               [1, 0, 0, 7, 0, 0, 0, 0, 0],
#               [0, 0, 4, 0, 0, 0, 2, 9, 0],
#               [8, 0, 0, 0, 0, 1, 0, 0, 0],
#               [0, 0, 0, 0, 3, 0, 6, 4, 0],
#               [3, 0, 0, 8, 0, 5, 0, 0, 0],
#               [0, 0, 0, 1, 0, 4, 0, 2, 0],
#               [0, 3, 0, 0, 0, 0, 0, 0, 0]]
#
# # 各块中元素的下标
# sudoku_block = []
# # 各元素所在块
# sudoku_in_block = [[0, 0, 0, 1, 1, 1, 2, 2, 2],
#                    [0, 0, 1, 1, 1, 2, 2, 2, 2],
#                    [3, 0, 0, 1, 1, 4, 4, 2, 2],
#                    [3, 3, 0, 0, 1, 4, 5, 5, 5],
#                    [3, 3, 3, 4, 4, 4, 5, 5, 5],
#                    [3, 3, 6, 6, 7, 4, 5, 5, 5],
#                    [3, 6, 6, 7, 7, 4, 4, 8, 8],
#                    [6, 6, 7, 7, 7, 8, 8, 8, 8],
#                    [6, 6, 6, 7, 7, 7, 8, 8, 8]]


def generate_sudoku_block():
    for i in range(N):  # 找第i个block中的元素
        temp = []
        for j in range(N):  # sudoku_in_block的行
            for p in range(N):  # sudoku_in_block的列
                if sudoku_in_block[j][p] == i:
                    temp.append([j, p])
        sudoku_block.append(temp)


def generate_candidate(blank):
    row = blank[0]
    col = blank[1]
    candidates = []
    for i in range(N):  # 初始化
        candidates.append(i + 1)
    for i in range(N):  # 行
        if sudoku_map[row][i]:
            if candidates.count(sudoku_map[row][i]):
                candidates.remove(sudoku_map[row][i])
    for i in range(N):  # 列
        if sudoku_map[i][col]:
            if candidates.count(sudoku_map[i][col]):
                candidates.remove(sudoku_map[i][col])
    block_index = sudoku_in_block[row][col]
    for i in range(N):  # 块
        row_num = sudoku_block[block_index][i][0]
        col_num = sudoku_block[block_index][i][1]
        if sudoku_map[row_num][col_num]:
            if candidates.count(sudoku_map[row_num][col_num]):
                candidates.remove(sudoku_map[row_num][col_num])
    return candidates


def get_blanks_in_map(new_map):
    num = 0
    for i in range(N):
        for j in range(N):
            if new_map[i][j] == 0:
                num += 1
    return num


def map_is_full(new_map):
    if get_blanks_in_map(new_map):
        return False
    else:
        return True


def is_legal(new_map):
    # 行
    for i in range(N):
        candidates = []
        # for num in range(N):  # 初始化
        #     candidates.append(num + 1)
        for j in range(N):
            if new_map[i][j]:
                candidates.append(new_map[i][j])
        len_candidates = len(candidates)
        if len_candidates != len(list(set(candidates))):
            return False
    # 列
    for i in range(N):
        candidates = []
        # for num in range(N):  # 初始化
        #     candidates.append(num + 1)
        for j in range(N):
            if new_map[j][i]:
                candidates.append(new_map[j][i])
        len_candidates = len(candidates)
        if len_candidates != len(list(set(candidates))):
            return False
    # 块
    for i in range(N):
        candidates = []
        # for num in range(N):  # 初始化
        #     candidates.append(num + 1)
        for j in range(N):
            row = sudoku_block[i][j][0]
            col = sudoku_block[i][j][1]
            if new_map[row][col]:
                candidates.append(new_map[row][col])
        len_candidates = len(candidates)
        if len_candidates != len(list(set(candidates))):
            return False
    return True


def find_blank(new_map):
    for i in range(N):
        for j in range(N):
            if new_map[i][j] == 0:
                return i, j


def dic_init():
    dic = {}
    for i in range(N):
        for j in range(N):
            dic[(i, j)] = 0
    return dic


def solve():
    new_map = copy.deepcopy(sudoku_map)
    num_of_blanks = get_blanks_in_map(sudoku_map)
    num_of_candidates = []
    max_loops = 1
    candidates_list = []
    blank_list = []
    for i in range(num_of_blanks):
        index = find_blank(new_map)
        new_map[index[0]][index[1]] = 1
        blank_list.append(index)
        candidates = generate_candidate(index)
        candidates_list.append(candidates)
        max_loops *= len(candidates)
        num_of_candidates.append(len(candidates))
    find_ans = False
    for i in range(max_loops):  # 第i+1次循环
        new_map = copy.deepcopy(sudoku_map)
        for j in range(num_of_blanks):  # 对每一种情况计算空格取值
            index = blank_list[j]
            dis = num_of_blanks - 1 - j
            # lambda1=1
            lambda2 = 1
            for temp in range(dis):
                lambda2 *= num_of_candidates[num_of_blanks - 1 - temp]
            lambda1 = lambda2 * num_of_candidates[num_of_blanks - 1 - dis]
            select = int(i % lambda1 / lambda2)  # 相当于进制的算法
            new_map[index[0]][index[1]] = candidates_list[j][select]
        if is_legal(new_map):
            find_ans = True
            break
    if find_ans:
        print('find an answer:')
        for i in range(N):
            print(new_map[i])
    else:
        print('no answer!')


if __name__ == '__main__':
    t_start = time.time()
    generate_sudoku_block()
    solve()
    t_end = time.time()
    print('time consumed:', t_end - t_start)
